/*
 * BinTree.c
 *
 *  Created on: Jan 29, 2012
 *      Author: Georgios
 */

#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>

#include "BinTree.h"


/*
 Given a binary tree, return true if a node
 with the target data is found in the tree. Recurs
 down the tree, chooses the left or right
 branch by comparing the target to each node.
*/
int Lookup(node_t *node, int target) {
  // 1. Base case == empty tree
  // in that case, the target is not found so return false
  if (node == NULL) {
    return 0;
  }
  else {
    // 2. see if found here
    if (target == node->data) {
    	return 1;
    }
    else {
      // 3. otherwise recur down the correct subtree
      if (target < node->data) {
    	  return Lookup(node->left, target);
      }
      else {
    	  return Lookup(node->right, target);
      }
    }
  }
}


/*
 Helper function that allocates a new node
 with the given data and NULL left and right
 pointers.
*/
node_t * NewNode(int data) {
	node_t *node = (node_t *) malloc(sizeof(node_t));

	node->data = data;
	node->left = NULL;
	node->right = NULL;

	return node;
}

/*
 Give a binary search tree and a number, inserts a new node
 with the given number in the correct place in the tree.
 Returns the new root pointer which the caller should
 then use (the standard trick to avoid using reference
 parameters).
*/
node_t * Insert(node_t *node, int data) {
	// 1. If the tree is empty, return a new, single node
	if (node == NULL) {
		return NewNode(data);
	} else {
		// 2. Otherwise, recur down the tree
		if (data <= node->data) {
			node->left = Insert(node->left, data);
		} else {
			node->right = Insert(node->right, data);
		}
		return node; // return the (unchanged) node pointer
	}
}


/*
 Compute the number of nodes in a tree.
*/
int Size(node_t * node) {
	if (node==NULL) {
		return(0);
	} else {
		return(Size(node->left) + 1 + Size(node->right));
	}
}


/*
 Compute the "maxDepth" of a tree -- the number of nodes along
 the longest path from the root node down to the farthest leaf node.
*/
int MaxDepth(node_t *node) {
	if (node==NULL) {
		return 0;
	}
	else {
		// compute the depth of each subtree
		int lDepth = MaxDepth(node->left);
		int rDepth = MaxDepth(node->right);
		// use the larger one
		if (lDepth > rDepth) {
			return lDepth+1;
		}
		else {
			return rDepth+1;
		}
	}
}


/*
 Given a non-empty binary search tree,
 return the minimum data value found in that tree.
 Note that the entire tree does not need to be searched.
*/
int MinValue(node_t *node) {
	node_t* current = node;
	// loop down to find the leftmost leaf
	while (current->left != NULL) {
		current = current->left;
	}
	return current->data;
}


/*
 Given a binary search tree, print out
 its data elements in increasing
 sorted order.
*/
void PrintTree(node_t *node) {
	if (node == NULL) {
		return;
	}
	PrintTree(node->left);
	printf("%d ", node->data);
	PrintTree(node->right);
}

/*
 *
 *


This tree is considered unbalanced because the root node has a balance factor of 2.
That is, the right subtree of 1 has a height of 2, and the height of 1's left subtree is 0.
Remember that balance factor of a tree with a left subtree A and a right subtree B is B - A.

Simple.
In figure 2-2, we see that the tree has a balance of 2.
This means that the tree is considered"right heavy".
We can correct this by performing what is called a "left rotation".
How we determine which rotation to use follows a few basic rules.
See psuedo code:
IF tree is right heavy {
	IF tree's right subtree is left heavy {
		Perform Double Left rotation
	} ELSE {
		Perform Single Left rotation
	}
} ELSE IF tree is left heavy {
	IF tree's left subtree is right heavy {
		Perform Double Right rotation
	} ELSE {
		Perform Single Right rotation
	}
}
}

 */

